package dp;

public class Fibonacci_509 {
    /**
     *  暴力递归，但凡遇到需要递归的问题，最好都画出递归树
     *  计算时间复杂度
     *  先计算子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)
     *  然后计算解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)。
     *  所以，这个算法的时间复杂度为二者相乘，即 O(2^n)，指数级别。
     *
     */
    public int fib1(int n) {
        if (n <= 1) {
            return n;
        }
        return fib1(n-1) + fib1(n-2);
    }

    /**
     * 带备忘录的递归解法
     * 即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；
     * 每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了
     * 可以用数组或哈希标充当备忘录
     * 子问题个数，即图中节点的总数，由于本算法不存在冗余计算，子问题就是 f(1), f(2), f(3) … f(20)，数量和输入规模 n = 20 成正比，所以子问题个数为 O(n)。
     * 解决一个子问题的时间，同上，没有什么循环，时间为 O(1)。所以，本算法的时间复杂度是 O(n)。空间复杂度也是O(n)
     * 带备忘录的解法与动态规划类似，只是一个是自顶向下，一个是自底向上
     * 画的递归树（或者说图）中是从上向下延伸，都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个 base case，然后逐层返回答案，这就叫「自顶向下」。
     * 直接从最底下，最简单，问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。
     */
    public int fib2(int n) {
        // 备忘录初始化默认全为0
        int[] memo = new int[n + 1];
        if (n <= 1) {
            return n;
        }
        return helper(n, memo);
    }

    public int helper(int n, int[] memo) {
        if (n <= 1) {
            return n;
        }
        if (memo[n] != 0) {
            return memo[n];
        }
        // 带备忘录的递归
        memo[n] = helper(n-1, memo) + helper(n-2, memo);
        return memo[n];
    }

    // 可以把备忘录独立出来成为dp table，自底向上，先计算出dp[0],dp[1],dp[2],直到最终结果
    public int fib3(int n) {
        if (n <= 1) {
            return n;
        }

        int[] dp = new int[n+1];
        // 确定base case
        dp[0] = 0;
        dp[1] = 1;

        // 状态转移方程，直接代表着暴力解法
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

    // 状态压缩，根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了，空间复杂度O(1)
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        int first = 0;
        int second = 1;
        int tmp = 0;
        // 状态转移方程，直接代表着暴力解法
        for (int i = 2; i <= n; i++) {
            tmp = first + second;
            first = second;
            second = tmp;
        }
        return second;
    }
}
